In the general network system, a user or subscriber of the network has a user's terminal, such as a personal computer, for connection to the network. A user's terminal is assigned hierarchically with a specific network address every internal user group in order to be distinguished from other user's terminals. Herein, a higher hierarchical user group has a shorter effective part of network address, on the other hand, a lower hierarchical user group has a longer one. Herewith, when communication data is transferred into a network device, such as network router, to control the transfer of communication data between a plurality of user's terminals in the network, the function that considers and compares the lengths of effective part of network addresses is indispensable to the processes for determination of transfer network address and transfer permission from the destination and source network addresses. The associative memory is used to carry out this function.
As an example of construction, the connection diagram of conventional computer network is shown in FIG. 24. A user's terminal for connection to the network, as described above, is assigned hierarchically with a network address every internal user group in accordance with a predetermined rule. Herein, the network address is represented by a numeral of a plurality of digits of, for example, first through fourth digits (a, b, c, d). The predetermined rule defines a hierarchical structure of the network address. For example, the first digit of the numeral represents a nation, such as England, Germany and Japan. The second digit of the numeral represents a city in the nation, the third digit of the numeral represents a company name in the city, and the final digit of the numeral distinguishes a user's terminal for connection to the network from other user's terminals in the company. In the following description, these hierarchical items will be called segments. Referring to FIG. 24, each segment is depicted by a rectangular block. Specifically, the SEGMENT1 that the first digit of network address is specified as “1”, the SEGMENT2 that the first digit of that is “2”, and the SEGMENT3 that the first digit of that is “3” exist as the highest segments.
The SEGMENT4 subordinate to the SEGMENT1 has a network address (1, 2, *, *) in which “1” and “2” are specified as the first and second digits, respectively. The SEGMENT6 subordinate to the SEGMENT4 has a network address (1, 2, 2, *) in which “1”, “2” and “2” are specified as the first through third digits, respectively. Thus, a user's terminal PC401-1 having a network address (1, 2, 2, 1) is connected in the SEGMENT6. As well as, the SEGMENT5 subordinate to the SEGMENT2 has a network address (2, 1, *, *) in which “2” and “1” are specified as the first and second digits, respectively. The SEGMENT7 subordinate to the SEGMENT5 has a network address (2, 1, 2, *) in which “2”, “1” and “2” are specified as the first through third digits, respectively. A user's terminal PC401-2 having a network address (2, 1, 2, 3) is connected in the SEGMENT7. Thus, the SEGMENT8 subordinate to the SEGMENT3 has a network address (3, 1, *, *) in which “3” and “1” are specified as the first and second digits, respectively. A symbol “*” contained in these addresses represents “don't care”.
In order to control the transfer of communication data between a plurality of user's terminals in the network, each segment is provided with a network device. As illustrated in FIG. 24, the SEGMENT1 is provided with the network device 400-1, the SEGMENT2 is provided with the network device 400-2, the SEGMENT3 is provided with the network device 400-3, the SEGMENT4 is provided with the network device 400-4, the SEGMENT5 is provided with the network device 400-5, the SEGMENT6 is provided with the network device 400-6, the SEGMENT7 is provided with the network device 400-7, and the SEGMENT8 is provided with the network device 400-8, respectively. Each network device in the corresponding segment has a function to calculate an optimum transfer route and transfer data to a receiver via the optimum transfer route thus calculated on the basis of the relationship of connection of network devices and the transfer address annexed to the communication data that is supplied from any use's terminals or any other network apparatuses connected to the network device. As illustrated in FIG. 24, each network device is connected to any user's terminals or any network devices subordinate to the corresponding segment In addition, the network device 400-3 is connected to the network device 400-1, the network device 400-6, the network device 400-2, and the network device 400-7.
Each digit of each network address is represented by a quaternary number of two bits. Thus, each network address is represented by a bit sequence of eight bits in total.
For example, a network address (1, 2, *, *) in quaternary is represented by a bit sequence (01, 10, 00, 00). Hereinafter, a bit sequence represented as above-mentioned representation is called a storage data. Since the symbol “*” represents “don't care” for each of third and fourth digits, it is necessary to indicate that the first through fourth bits (01, 10) in the bit sequence (01, 10, 00, 00) alone are valid and the remaining bits (00, 00) are invalid. For this purpose, mask information (or mask data) is combined with the storage data. Hereinafter, the combined data is called structured data.
In the illustrated example, the mask information (or mask data) is given by a bit sequence (11, 11, 00, 00). Herein, “1” and “0” represent a mask invalid state and a mask valid state, respectively. The invalid state “0” of storage data is stored in the bits of storage data corresponding to the mask information (or mask data) that the mask is valid.
The network device has some functions to control communication data stored in the segments. There are the function to calculate the determination of transfer permission on the basis of the source network address and destination network address annexed to the communication data, which is supplied from any use's terminals, and the predetermined transfer rule and the function to calculate an optimum transfer route and create the transfer network address on the basis of the above-mentioned source network address and the relationship of connection of network devices.
Referring to FIG. 24, for example, when the network device 400-3 transfers communication data to a user's terminal PC401-2 having a destination network address (2, 1, 2, 3) expressed as digits in the quaternary system, as it may be clearly realized from the figure, the optimum transfer route is not to the network device 400-2 having a network address (2, *, *, *) displayed in the quaternary system, but to the network device 400-7 having a network address (2, 1, 2, *) displayed in the quaternary system. Therefore, it is optimum to select a network device having the mask information (data) that the number of valid mask bits is minimum in the network address among the network devices having same digit of the network address as compared with the destination network address in consideration of the mask information (data).
Thus, the limited communication channels are effectively used for extra safety to carry out communication by controlling the transfer of communication data between the network devices without connecting the user's terminals directly by the use of the communication channels.
Next referring to FIG. 25, the typical conventional network device will be described.
This figure is a block diagram of a conventional network device. In FIG. 25, the system and operation of conventional network device 400 is explained with an example of being applied to the network device 400-3 described in FIG. 24.
The input communication data 407 is entered into the network device 400, and the output communication data 408 is transferred from the network device 400. The input communication data 407 includes the source network address 409, the transfer network address 410 and the destination network address 411. And also, the output communication data 408 includes the source network address 409, the second transfer network address 412 and the destination network address 411. Since FIG. 25 describes the case that the conventional network device 400 is applied to the network device 400-3 illustrated in FIG. 24, the transfer network address 410 included in the input communication data 407 is set naturally as a network address in the network device 400-3.
The network device 400 consists of the destination network address extracting section 405, the associative memory 300, the encoder 308, the transfer network address storage memory 402, and the transfer network address changing section 406. The destination network address extracting section 405 extracts the destination network address 411 from the input communication data 407, and enters this address as the search data 307 into the associative memory 300.
Outside the segment to which the network device 400 belongs in the network, the network address for the segment to which other network device connecting with the network device 400 belongs is stored into the associative memory words 305-0, 305-1, 305-2 and 305-3 of the associative memory 300, respectively. Since FIG. 25 describes the case that the conventional network device 400 is applied to the network device 400-3 illustrated in FIG. 24, the first associative memory word 305-0 stores the network address (1, *, *, *) displayed in the quaternary system for the segment 1 to which the network device 400-1 belongs by use of the structured data system that the storage data (01, 00, 00, 00) is combined with the mask information (11, 00, 00, 00) as mentioned above. In the same way, the second associative memory word 305-1 stores the network address (2, *, *, *) displayed in quaternary for the segment 2 to which the network device 400-2 belongs, the third associative memory word 305-2 stores the network address (1, 2, 2, *) displayed in quaternary for the segment 6 to which the network device 400-6 belongs, and the fourth associative memory word 305-3 stores the network address (2, 1, 2, *) displayed in quaternary for the segment 7 to which the network device 400-7 belongs. As well as the ordinary memory, the associative memory 300 has the normal function to specify a network address and enter/load the storage data and also the specific mask searching function to put the only mask match line 301 corresponding to the storage data with the least number of bits in a mask valid state, in the mask match lines 301-0 to 301-3 corresponding to one of the storage data coincident with the search data 307 taking the mask information into account, into a valid state. According to the definition of structured data system, this function is equivalent to other function to put the only mask match line 301 corresponding to the storage data with the least number of bits in a storage data invalid state, in the mask match lines 301-0 to 301-3 corresponding to one of the storage data coincident with the search data 307 taking the mask information into account, into a valid state. As the typical conventional associative memory 300, for example, the Japanese Patent Application No. 2000-181406, No. 2000-243485 and the International Patent Application No. PCT/JP01/03562 are disclosed.
The encoder 308 encodes the match lines 301-0 through 301-3 that the associative memory 300 supplies into an address output signal 309. The transfer network address storage memory 402 stores the network address of network device corresponding to the segment network addresses each of which is stored in the associative memory words 305-0 through 305-3 of the associative memory 300 by use of the structured data system and each of which is stored in the associative memory words 403-0 through 403-3 of the associative memory 300. For example, the network address (1, *, *, *) expressed in the quaternary system is stored in the first associative memory word 305-0 of the associative memory 300 while the network address of network device 400-1 (FIG. 24) corresponding thereto is stored in the first memory word 403-0 of the transfer network address storage memory 402. Similarly, the network address of network device 400-2, the network address of network device 400-6, and the network address of network device 400-7 are stored in the second memory word 403-1, the third memory word 403-2, and the fourth memory word 403-3 of the transfer network address storage memory 402, respectively. Supplied with the address output signal 309 as a read address, the transfer network address storage memory 402 produces a memory data signal 404 stored in the word designed by the memory address signal 309.
The transfer network address changing section 406 changes the transfer network address 410 of the input communication data 407 to the second transfer network address 412 according to the memory data signal 404 and transfers the output communication data 408 to a network device corresponding to the second transfer network address 412.
It is assumed here that the input communication data 407 has the destination network address 411 (1, 2, 2, 1) in the quaternary system. On the completion of search by the associative memory 300, only the match line 301-2 corresponding to the network address (1, 2, 2, *) in quaternary stored in the third associative memory word 305-2 is put into a valid state. Therefore, the encoder 308 produces “2” in a decimal system as the address output signal 309. In response to the address output signal 309, the transfer network address storage memory 402 produces as the memory data signal 404 the network address for the network device 400-6. The transfer network address changing section 406 sets the network address for the network device 400-6 as the second transfer network address 412 of the output communication data 408, and transfers the output communication data 408 to the network device 400-6.
[Description of Typical Conventional Associative Memory]
Herein, referring to FIG. 23, a typical conventional associative memory will be described. As an example, FIG. 23 describes the system and operation of the conventional associative memory that is applied to the network device 400-3 illustrated in FIG. 24. It is assumed here that the associative memory 300 comprises four words of eight bits.
The associative memory 300 consists of the primary searching associative memory 302 comprising four words of eight bits and the secondary searching associative memory 303 comprising four words of eight bits. The primary searching associative memory 302 is provided with the primary associative memory words 305-0 through 305-3 that can store the structured data consisting of each 8-bit storage data and mask information (data).
Hereupon, the symbol “*” represents “don't care” for the bits of structured data with the corresponding bit of storage data put in the invalid state and the corresponding bit of mask information (data) put in the valid state. The primary searching associative memory 302 carries out the primary search for the storage data coincident with the search data 307 taking the mask information into account, performs the logical sum operation for the coincident storage data in the confirmed valid state, and produces the calculated values as the intermediate data 304-1 through 304-8. The secondary searching associative memory 303 is provided with the associative memory words 306-0 through 306-3 storing as the secondary storage data the same state of each 8-bit storage data stored in the corresponding primary associative memory words 305-0 through 305-3, carries out the secondary search for the secondary storage data coincident with the 8-bit intermediate data 304-1 through 304-8, and makes valid the match lines 301-0 through 301-3 corresponding to the associative memory words 306-0 through 306-3 storing the coincident secondary storage data. The encoder 308 encodes the match lines 301-0 through 301-3 into an address output signal 309 to access the memory that is not illustrated. However, the encoder 308 is not required to have any priority function.
In this example, a valid state and an invalid state are represented by “0” and “1”, respectively, for the mask information, but a valid state and an invalid state are represented by “1” and “0”, for the storage data, respectively. As well as the storage data, a valid state and an invalid state are represented by “1” and “0”, respectively, for the intermediate data 304-1 through 304-8, and the match lines 301-0 through 301-3.
Hereupon, the connection information other than the in-quaternary network address (3, *, *, *) of the network device 400-3 as well as FIG. 25 shall be memorized in the storage data and mask information (data) stored in the primary associative memory words 305-0 through 305-3 of the primary searching associative memory 302. At this time, the symbol “*” represents “don't care” for the bits of connection information with the corresponding bit of mask information (data) put in the valid state “0”. The invalid state “0” of storage data is stored in the corresponding bit of data.
Specifically, the primary associative memory word 305-0 stores in binary the storage data (01, 00, 00, 00) and the mask information (11, 00, 00, 00) to represent (1, *, *, *) in quaternary. Likewise, the primary associative memory word 305-1 stores in binary the storage data (10, 00, 00, 00) and the mask information (11, 00, 00, 00) to represent (2, *, *, *) in quaternary. The primary associative memory word 305-2 stores in binary the storage data (01, 10, 10, 00) and the mask information (11, 11, 11, 00) to represent (1, 2, 2, *) in quaternary. The primary associative memory word 305-3 stores in binary the storage data (10, 01, 10, 00) and the mask information (11, 11, 11, 00) to represent (2, 1, 2, *) in quaternary.
The primary searching associative memory 302 carries out, among the primary associative memory words 305-0 through 305-3, the primary search for the storage data coincident with the search data 307 supplied from an external source, taking the mask information into account. As well as the above-mentioned operation system of the conventional network device, FIG. 23 describes the operation system in which the in-quaternary network address (1, 2, 2, 1) of a user's terminal PC401-2 in FIG. 24 is entered as the search data 307. At this time, both the in-quaternary network address (1, *, *, *) stored in the primary associative memory word 305-0 and the in-quaternary network address (1, 2, 2, *) stored in the primary associative memory word 305-2 are coincident with the network address (1, 2, 2, 1) f the search data 307 as the result of primary search. The primary searching associative memory 302 performs the logical sum operation for the in-binary storage data (01, 00, 00, 00) and (01, 10, 10, 00) stored in the primary associative memory words 305-0 and 305-2 coincident with the search data 307 with the storage data confirmed in the valid state, and produces the calculated 8-bit state (01, 10, 10, 00) as the intermediate data 304-1 through 304-8.
The same storage data stored in the primary associative memory words 305-0 through 305-3 corresponding to the primary searching associative memory 302 is stored as the secondary storage data in the associative memory words 306-0 through 306-3 of the secondary searching associative memory 303. In other words, the associative memory words 306-0, 306-1, 306-2 and 306-3 store in binary the storage data (01, 00, 00, 00), (10, 00, 00, 00), (01, 10, 10, 00) and (10, 01, 10, 00), respectively.
The secondary searching associative memory 303 carries out, among the associative memory words 306-0 through 306-3, the secondary search for the secondary storage data coincident with all bits of (01101000) expressed in binary in the intermediate data 304-1 through 304-8 supplied from the primary searching associative memory 302. In this example, the associative memory word 306-2 is completely coincident with the secondary storage data to be stored, and supplies the valid state “1” to the corresponding match line 301-2. The invalid state “0” is supplied to other match lines 301-0, 301-1 and 301-3 that are not coincident correspondingly. The encoder 308 encodes the match lines 301-0 through 301-3 (0100) supplied from the associative memory 300, and then produces the address output signal 309 translated from “10” expressed in binary (“2” in decimal).
Therefore, the associative memory 300 can put the only match line 301-2 corresponding to the storage data with the least number of bits in a mask valid state or non-mask invalid state, in the storage data coincident with the search data 307 taking the mask information into account, into a valid state. This indicates that even the encoder 308 without a priority function correctly supplies the address output signal 309 translated from “2” expressed in decimal. In addition, it indicates that the structured data stored in the primary associative memory words 305-0 through 305-3 without putting data into order at random as mentioned above can be correctly obtained regardless of the order of storing data.
The conventional associative memory 300 cannot produce the correct address output signal without putting the structured data into order to store and using the encoder with the priority function in order to connect a plurality of the associative memory 300 to increase the data storage capacity as described below.
FIG. 26 describes the first example of system and operation of the conventional associative memories 300-0 and 300-1 that are connected. As well as the description of FIG. 23, in this example, it is assumed here that each of the associative memories 300-0 and 300-1 comprises four words of eight bits and the associative memory 300-1 reserves the top of the address space. As a result, the storage capacity of two associative memories is eight words in total.
The search data 307 is entered into all of the associative memories 300-0 and 300-1 that are connected. The associative memories 300-0 and 300-1 send the search data 307 to the priority-less encoder 310 via the match lines 301-0-0 through 301-3-0 and the match lines 301-0-1 through 301-3-1, respectively. The encoder 310 encodes the match lines 301-0-0 through 301-3-1 into an address output signal 309 to access the memory that is not illustrated.
The associative memory 300-0 consists of the primary searching associative memory 302-0 and the secondary searching associative memory 303-0. The intermediate data of 304-1-0 through 304-8-0 is transferred from the primary searching associative memory 302-0 to the secondary searching associative memory 303-0. As well as the description of FIG. 23, it is assumed here that the primary associative memory words 305-0-0 through 305-3-0 of the primary searching associative memory 302-0 store the storage data and mask information (data) so as to represent (1, *, *, *), (2, *, *, *), (1, 2, 2, *) and (2, 1, 2, *) in quaternary as the structured data, respectively. And also, as well as the description of FIG. 23, it is assumed here that the associative memory words 306-0-0 through 306-3-0 of the secondary searching associative memory 303-0 store the same secondary storage data (1, 0, 0, 0), (2, 0, 0, 0), (1, 2, 2, 0) and (2, 1, 2, 0) in quaternary as the storage data, respectively, that are stored in the primary associative memory words 305-0-0 through 305-3-0 of the primary searching associative memory 302-0.
The associative memory 300-1 consists of the primary searching associative memory 302-1 and the secondary searching associative memory 303-1. The intermediate data of 304-1-1 through 304-8-1 is transferred from the primary searching associative memory 302-1 to the secondary searching associative memory 303-1. Since this content is not referred to the connection system of network devices shown in FIG. 24, it is assumed here that the primary associative memory words 305-0-1 through 305-3-1 of the primary searching associative memory 302-1 store the storage data and mask information (data) so as to represent (3, 1, *, *), (1, 2, *, *), (2, 1, *, *) and (3, *, *, *) in quaternary as the structured data, respectively. And also, it is assumed here that the associative memory words 306-1 through 306-3-1 of the secondary searching associative memory 303-1 store the same secondary storage data (3, 1, 0, 0), (1, 2, 0, 0), (2, 1, 0, 0) and (3, 0, 0, 0) in quaternary as the storage data, respectively, that are stored in the primary associative memory words 305-0-1 through 305-3-1 of the primary searching associative memory 302-1.
Hereunder, the description will proceed to input of as the search data 307 the network address (2, 1, 2, 3), expressed in quaternary, of the user's terminal (PC) 401-2 shown in FIG. 24.
In the associative memory 300-0, at the first, the primary searching associative memory 302-0 carries out the primary search for the storage data coincident with the search data 307 taking the mask information into account, and as a result, the structured data (2, *, *, *) and (2, 1, 2, *) in quaternary stored in the primary associative memory words 305-1-0 and 305-3-0, respectively, are coincident with the search data 307. The primary searching associative memory 302-0 performs the logical sum operation for the in-quaternary storage data (2, 0, 0, 0) and (2, 1, 2, 0) stored in the primary associative memory words 305-1-0 and 305-3-0, respectively, coincident with the search data 307 with the storage data confirmed in the valid state, and produces the calculated 8-bit state of (2, 1, 2, 0), expressed in quaternary, as the intermediate data 304-1-0 through 304-8-0, into the secondary searching associative memory 303-0. The secondary searching associative memory 303-0 carries out the secondary search for the secondary storage data that is completely coincident with the intermediate data 304-1-0 through 304-8-0, and as a result, only the secondary storage data stored in the associative memory word 306-3-0 is coincident with the in-quaternary storage data (2, 1, 2, 0). The secondary searching associative memory 303-0 supplies the valid state “1” to the corresponding match line 301-3-0 and the invalid state “0” to other match lines 301-0-0, 301-1-0 and 301-2-0. Like the above, the associative memory 300-0 itself can put the only match line 301-3-0 corresponding to the storage data with the least number of bits in a mask valid state in the storage data coincident with the search data 307 taking the mask information into account, into a valid state.
In the associative memory 300-1, at the first, the primary searching associative memory 302-1 carries out the primary search for the storage data coincident with the search data 307 taking the mask information into account, and as a result, the structured data (2, 1, *, *) in quaternary stored in the primary associative memory words 305-2-1 is coincident with the search data 307. The primary searching associative memory 302-1 produces the in-quaternary storage data (2, 1, 0, 0) stored in the primary associative memory word 305-2-1 coincident with the search data 307 as the intermediate data 304-1-1 through 304-8-1, into the secondary searching associative memory 303-1. The secondary searching associative memory 303-1 carries out the secondary search for the secondary storage data that is completely coincident with the intermediate data 304-1-1 through 304-8-1, and as a result, only the secondary storage data stored in the associative memory word 306-2-1 is coincident with the in-quaternary storage data (2, 1, 0, 0). The secondary searching associative memory 303-1 supplies the valid state “1” to the corresponding match line 301-2-1 and the invalid state “0” to other match lines 301-0-1, 301-1-1 and 301-3-1. Like the above, the associative memory 300-1 itself can put the only match line 301-2-1 corresponding to the storage data with the least number of bits in a mask valid state in the storage data coincident with the search data 307 taking the mask information into account, into a valid state.
Here, the two match lines 301-3-0 and 301-2-1 among the match lines 301-0-0 through 301-3-1 connecting to the encoder 310 are put into the valid state “1”. Therefore, the priority-less encoder 310 comes to produce “undefined” as the address output signal 309. Even if the encoder 310 is provided with the priority function to give priority to the top address, it would produce “110” in binary or “6” in decimal as the address output signal 309.
This indicates an incorrect content that the value “110” in binary is different from “011” in binary corresponding to the primary associative memory word 305-3-0 storing the optimum structured data (2, 1, 2, *) in quaternary as realized clearly from the figure.As a result, it indicates that the correct data cannot be obtained when the structured data is stored into the primary associative memory words 305-0-0 through 305-3-1 without putting data into order at random as the first example of system and operation of a plurality of conventional associative memories connected shown in FIG. 26.
FIG. 27 describes the second example of system and operation of a plurality of the conventional associative memories 300-0 and 300-1 that are connected. As well as the description of FIG. 26, in this example, it is assumed here that each of the associative memories 300-0 and 300-1 comprises four words of eight bits and the associative memory 300-1 reserves the top of the address space.
As well as FIG. 26, the search data 307 is entered into all of the associative memories 300-0 and 300-1 that are connected. The associative memories 300-0 and 300-1 send the search data 307 to the address signal producing section 319 via the match lines 301-0-0 through 301-3-0 and the match lines 301-0-1 through 301-3-1, respectively. The address signal producing section 319 encodes the match lines 301-0-0 through 301-3-1 into an address output signal 309 to access the memory that is not illustrated.
The associative memories 300-0 and 300-1 are constructed just as well as FIG. 26.
However, it is assumed here that the structured data is stored into the primary associative memory words 305-0-0 through 305-3-1 according to the order after putting data into order from smaller to larger values that are assumed to be the value of storage data. As an example of eight pieces of the structured data described as well as FIG. 26, the primary associative memory word 305-0-0 stores the storage data and mask information (data) to represent the in-quaternary structured data (1, *, *, *) that is the minimum storage data (1, 0, 0, 0) expressed in quaternary. Hereunder, the primary associative memory words 305-1-0, 305-2-0, 305-3-0, 305-0-1, 305-1-1, 305-2-1 and 305-3-1 store the storage data and mask information (data) to represent the in-quaternary structured data (1, 2, *, *), (1, 2, 2, *), (2, *, *, *), (2, 1, *, *), (2, 1, 2, *), (3, *, *, *) and (3, 1, *, *) in order, respectively.
The associative memory words 306-0-0 through 306-3-1 of the secondary searching associative memories 303-0 and 303-1 store the same secondary storage data as the storage data stored in the primary associative memory words 305-0-0 through 305-3-1 of the primary searching associative memories 302-0 and 302-1. Therefore, the associative memory words 306-0-0 through 306-3-1 store the in-quaternary (1, 0, 0, 0), (1, 2, 0, 0), (1, 2, 2, 0), (2, 0, 0, 0), (2, 1, 0, 0), (2, 1, 2, 0), (3, 0, 0, 0) and (3, 1, 0, 0) in order, respectively.
Every the associative memory 300-k (k=0 or 1), the address signal producing section 319 is provided with the encoder 311-k and the match searching means 313-k to encode the match lines 301-0-k through 301-3-k and also, provided with the priority encoder 315 and the selecting means 316.
The encoder 311-k encodes the match lines 301-k through 301-3-k supplied and produces the encoded one as the matched address signal 312-k to the selecting means 316.
When the match lines 301-0-k through 301-3-k include one or more valid-state signals, the match searching means 313-k produces the valid state “1” of match line to the match searching signal 314-k. Otherwise, the invalid state “0” of match line is produced to the match searching signal 314-k. Thus, the match searching means 313-k can be constructed by the logical sum operation unit, for example, with the match line confirmed in the valid state.
The priority encoder 315 receives the match searching signals 314-0 and 314-1 and produces the encoded one as the top address signal 317 to the selecting means 316 and also, to the external section from the address signal producing section 319. When the match searching signals 314-0 and 314-1 include more than one valid-state signal, priority is given to the match searching signal 314 corresponding to the associative memory 300 that is assigned to the top of address space.
The selecting means 316 selects the matched address signal 312, among the matched address signals 312-0 through 312-1 entered, corresponding to the top address signal 317 supplied from the priority encoder 315, and produces the matched address signal 312 as the low address signal 318 to the external section from the address signal producing section 319.
The top address signal 317 and the low address signal 318 transferred from the address signal producing section 319 are concatenated to the top side and low side of address output signal 309, respectively, becoming the address signals to access the memory that is not illustrated.
Hereunder, as well as the description in FIG. 26, the description will proceed to input of as the search data 307 the network address (2, 1, 2, 3), expressed in quaternary, of the user's terminal (PC) 401-2 shown in FIG. 24.
In the associative memory 300-0, at the first, the primary searching associative memory 302-0 carries out the primary search for the storage data coincident with the search data 307 taking the mask information into account, and as a result, the structured data (2, *, *, *) in quaternary stored in the primary associative memory word 305-3-0 is coincident with the search data 307. The primary searching associative memory 302-0 produces as the intermediate data 304-1-0 through 304-8-0 the in-quaternary storage data (2, 0, 0, 0) stored in the primary associative memory word 305-3-0 coincident with the search data 307, into the secondary searching associative memory 303-0. The secondary searching associative memory 303-0 carries out the secondary search for the secondary storage data that is completely coincident with the intermediate data 304-1-0 through 304-8-0, and as a result, only the secondary storage data stored in the associative memory word 306-3-0 is coincident with the intermediate data 304-1-0 through 304-8-0. The secondary searching associative memory 303-0 supplies the valid state “1” to the corresponding match line 301-3-0 and the invalid state “0” to other match lines 301-0-0, 301-1-0 and 301-2-0.
Like the above, the associative memory 300-0 itself can put the only match line 301-3-0 corresponding to the storage data with the least number of bits in a mask valid state in the storage data coincident with the search data 307 taking the mask information into account, into a valid state.
In the associative memory 300-1, at the first, the primary searching associative memory 302-1 carries out the primary search for the storage data coincident with the search data 307 taking the mask information into account, and as a result, the structured data (2, 1, *, *) and (2, 1, 2, *) in quaternary stored in the primary associative memory words 305-0-1 and 305-1-1, respectively, are coincident with the search data 307. The primary searching associative memory 302-1 performs the logical sum operation for the in-quaternary storage data (2, 1, 0, 0) and (2, 1, 2, 0) stored in the primary associative memory words 305-0-1 and 305-1-1, respectively, coincident with the search data 307 with the storage data confirmed in the valid state, and produces the calculated 8-bit state of (2, 1, 2, 0), expressed in quaternary, as the intermediate data 304-1-1 through 304-8-1, into the secondary searching associative memory 303-1. The secondary searching associative memory 303-1 carries out the secondary search for the secondary storage data that is completely coincident with the intermediate data 304-1-1 through 304-8-1, and as a result, only the secondary storage data stored in the associative memory word 306-1-1 is coincident with the intermediate data 304-1-1 through 304-8-1. The secondary searching associative memory 303-1 supplies the valid state “1” to the corresponding match line 301-1-1 and the invalid state “0” to other match lines 301-0-1, 301-2-1 and 301-3-1. Like the above, the associative memory 300-1 itself can put the only match line 301-1-1 corresponding to the storage data with the least number of bits in a mask valid state in the storage data coincident with the search data 307 taking the mask information into account, into a valid state.
Here, only the match line 301-3-0 among the match lines 301-0-0 through 301-3-0 connecting to the address signal producing section 319 is put into the valid state “1”.
Only the match line 301-1-1 among the match lines 301-0-1 through 301-3-1 is put into the valid state “1”. Therefore, the priority-less encoder 311-0 corresponding to the associative memory 300-0 produces “11” expressed in binary as the matched address signal 312-0, into the selecting means 316, and then, the match searching means 313-0 puts the match searching signal 314-0 in the valid state “1”. The priority-less encoder 311-1 corresponding to the associative memory 300-1 produces “01” expressed in binary as the matched address signal 312-1, into the selecting means 316, and then, the match searching means 313-1 puts the match searching signal 314-1 in the valid state “1”.
Since the two match searching signals 314-0 and 314-1 transferred to the priority encoder 315 are put in the valid state “1”, the priority encoder 315 gives priority to the match searching signal 314-1 corresponding to the associative memory 300-1 that is assigned to the top of address space. As a result, the priority encoder 315 produces “1” expressed in binary as the top address signal 317 to the selecting means 316 and also, to the external section from the address signal producing section 319.
The selecting means 316 selects the matched address signal 312-1, “01” expressed in binary, corresponding to the top address signal 317, “1” expressed in binary, supplied from the priority encoder 315, and produces the matched address signal 312-1 as the low address signal 318 to the external section from the address signal producing section 319.
The top address signal 317, “1” expressed in binary, and the low address signal 318, “01” expressed in binary, transferred from the address signal producing section 319 are concatenated to the top side and low side of address output signal 309, respectively, becoming “101” expressed in binary. In other words, in FIG. 27 showing the second example of system and operation of a plurality of the conventional associative memories connected, which is different from in FIG. 26, the in-binary value “101” corresponding to the primary associative memory word 305-1-1 storing the optimum structured data (2, 1, 2, *) in quaternary is obtained as the correct address output signal 309.
Thus, when a plurality of the associative memories 300 are connected to increase the data storage capacity regardless of the correct search result that the single associative memory 300 can obtain even if the structured data is stored in the primary associative memory word 305 without putting data into order at random, the structured data must be stored into the primary associative memory word 305 according to the order after putting data into order from smaller to larger values that are assumed to be the value of storage data in the structured data by the CPU (Central Processing Unit) that is not illustrated.
For example, when the associative memory 300 is used to calculate the transfer network address shown in FIG. 25, the additional connection and disconnection between the network devices are frequently carried out to modify the connection conditions of them, so that it is necessary for the network devices to transmit the connection conditions of them each other in a fixed cycle in order to reflect the modification in the network system and update the structured data stored in the associative memory 300. However, for example, the Internet communication system treats more than 100,000 words in the connection conditions, requires some seconds to put data into order even by using the high-speed CPU, and there was a problem that the network devices cannot perform the data transfer operation during the time of putting data into order.
In addition, there was a problem that connecting a plurality of the associative memories 300 must introduce the expensive high-speed CPU system that is not needed to use a single associative memory 300 with a boost in total price of network devices.
And also, the priority encoder 315 is required to produce the top address signal 317 to distinguish the associative memories 300 that reserve the top addresses in the address space, among the associative memories 300 putting even one match line 301 in the valid state in the address signal producing section 319, and in comparison with an ordinary encoder, only the area for a part of priority function becomes larger together with the remarkably long time of encoding operation. Thus, there was a problem that the system operation speed also becomes lower with a boost in total price of network devices.
Further, there was a problem that the network device using the associative memory 300 cannot increase the data storage capacity only by adding the associative memory 300 simply due to the needs of putting data into order as described above.
It is therefore an object of this invention to provide an associative memory system which consists of a plurality of associative memories and is able to select and produce an optimum piece of data at the high speed among a plurality of storage data coincident with the search data at the time of search operation even if the storage data is written, updated or eliminated without putting data into order.
It is another object of this invention to reduce the total cost of network devices.
It is another object of this invention to provide the network devices that can eliminate, add and modify the data stored in the associative memory without discontinuing the data transfer operation.
It is another object of this invention to provide the network devices that do not need the priority encoder.
It is another object of this invention to provide the network devices that can add or eliminate the associative memory easily according to the increase or decrease of data storage capacity.
It is another object of this invention to provide the network system that can transfer data at the high speed.